package com.xiyou.leetcode;

/**
 * 背包问题：
 * 5kg的袋子
 * 物品：
 * 钱：6  10  12
 * Kg：1  2   4
 */
public class MaxPricePackage {
    public static void main(String[] args) {
        // 定义物品的价值
        int value[] = {6, 10, 12};
        // 定义物品的重量
        int weight[] = {1, 2, 4};
        // 定义背包的容量
        int w = 5;
        // 定义物品的数量
        int n = 3;
        // 定义当前存放了几个物品重量是多少的最大价值
        int dp[][] = new int[n + 1][w + 1];

        // 背包拆分 从背包只有1kg开始算
        for (int tmpWeight = 1; tmpWeight <= w; tmpWeight++) {
            // 每次加的物品 一个物品一个物品往里面放
            for (int i = 1; i <= n; i++) {
                if (tmpWeight - weight[i - 1] >= 0) {
                    // 可以存放下
                    dp[i][tmpWeight] = Math.max(value[i - 1] + dp[i - 1][tmpWeight - weight[i - 1]], dp[i - 1][tmpWeight]);
                } else {
                    // 背包容量不够 就是取上一次的重量
                    dp[i][tmpWeight] = dp[i - 1][tmpWeight];
                }
            }
        }

        // 现在里面存的就是最大的重量
        System.out.println(dp[n][w]);
    }
}
